package leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class _0018 {
    /**
     * 四数之和
     */
    class Solution {
        public List<List<Integer>> fourSum(int[] nums, int target) {
            Arrays.sort(nums);
            int n= nums.length;
            List<List<Integer>> list = new ArrayList<>();
            for(int i=0;i<n-3;i++){
                long x = nums[i];
                if(i>0&&x==nums[i-1]){
                    continue;
                }
                if  (x+nums[n-1]+nums[n-2]+nums[n-3]<target){
                    continue;
                }
                if(x+nums[i+1]+nums[i+2]+nums[i+3]>target){
                    break;
                }
                for(int b = i+1;b<n-2;b++){
                    long y = nums[b];
                    if(b>i+1&&y==nums[b-1]){
                        continue;
                    }
                    if(y+nums[n-1]+nums[n-2]<target-x){
                        continue;
                    }
                    if(y+nums[b+1]+nums[b+2]>target-x){
                        break;
                    }
                    int left = b+1;
                    int right = n-1;
                    while(left<right){
                        long sum = nums[left]+nums[right];
                        if(sum+y>target-x){
                            right--;

                        }else if(sum+y<target-x){
                            left++;
                        }else{
                            List<Integer> l = new ArrayList<>();
                            l.add((int)x);
                            l.add((int)y);
                            l.add(nums[left]);
                            l.add(nums[right]);
                            list.add(l);
                            right--;
                            while(right>left&&nums[right]==nums[right+1]){
                                right--;
                            }
                            left++;
                            while(left<right&&nums[left]==nums[left-1]){
                                left++;
                            }
                        }
                    }
                }
            }
            return list;
        }
    }
}
